'''
@Descripttion: 
@version: 
@encoding: utf-8
@Author: qiurongcan
Date: 2025-09-08 14:41:11
LastEditTime: 2025-09-08 14:51:57
'''

# 多维动态规划


class Solution:
    
    def uniquePaths(self, m, n):

        dp = [[1] * n] + [[1] + [0] * (n-1) for _ in range(m - 1)]
        # 创建一个如下格式列表
        """
        1 1 1 1 1
        1 0 0 0 0
        1 0 0 0 0
        """
        for i in range(1, m):
            for j in range(1, n):
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1]
        
        return dp[-1][-1]
    

if __name__ == "__main__":

    m = 7
    n = 3
    sol = Solution()
    res = sol.uniquePaths(m, n)
    print(res)




